/*
 * @lc app=leetcode.cn id=2170 lang=cpp
 *
 * [2170] 使数组变成交替数组的最少操作数
 */

// @lc code=start
class Solution
{
public:
    typedef pair<int, int> PII;
    void getMaxNum(vector<int> &nums, int p, PII &z1, PII &z2)
    {
        unordered_map<int, int> m;
        int n = nums.size();
        for (int i = p; i < n; i += 2)
        {
            m[nums[i]]++;
        }
        for (auto &x : m)
        {
            if (x.second > z1.second)
            {
                z2 = z1;
                z1 = x;
            }
            else if (x.second > z2.second)
            {
                z2 = x;
            }
        }
    }
    int minimumOperations(vector<int> &nums)
    {
        int n = nums.size();
        if (n == 1)
            return 0;

        PII x1 = {0, 0}, x2 = {0, 0}, y1 = {0, 0}, y2 = {0, 0};
        getMaxNum(nums, 0, x1, x2);
        getMaxNum(nums, 1, y1, y2);

        int n0 = (n + 1) / 2, n1 = n - n0;
        if (x1.first != y1.first)
        {
            return (n0 - x1.second) + (n1 - y1.second);
        }

        return min(
            (n0 - x1.second) + (n1 - y2.second),
            (n0 - x2.second) + (n1 - y1.second));
    }
};
// @lc code=end
